很多东西都是可以用状态机去表示的, 如一个开灯的开关, 如果在关灯状态, 则按开灯灯就打开, 按关灯按钮, 状态不变. 如果在开灯状态, 按关灯按钮会转跳到关灯状态, 按开灯按钮状态不变.

状态机通常会有一个特殊的状态是Accept状态, 如果最终指令执行完, 停在了这个状态, 则最终输出Accept, 否则输出reject.
并且, 状态机是可以被语言表示的, 比如我们可以设计出一种状态机, 它只会接受以下这种语言
我们就可以说M recognizes 这个语言.
每种状态机只会认识一种语言, 我们记作L(M) 如果这个状态机不接受任何字符串, 则这个L(M)是个空集.

我们可以把这个L(M)完全当作一个Language, 所以可以说

反过来, 如果一个语言可以被状态机所recognized, 则这个语言可以说是regular language
如:
是一种regular language, 而

不是个regular language, 之后会证明它为什么不是

需要注意的是, 每个状态机只会识别一个Language, 如果一个状态机识别集合A, 但有个集合B, 它是A的子集, 我们仍然不能说状态机识别B, 只能说它接受B. 因为如果需要识别, 则这个集合需要包含这个机器M所接受的所有字符串

k-tuple - a sequence of k elements, k≥1
对于一个有限元自动机M, 它有五个元组:

如果一个状态机的F是空集, 那么它是没有终点, 也就是说它不会接受任何字符串, 所以它识别的语言也是空集

这是一种对于language的操作:

Union:
Concatenation:
◦

Star:
并且, 空字符串也会在这个合集里面, 因为k可以是0

前面两个都比较好理解, 最后一个就是把A合集里任意多的元素以任意顺序和任意数量组合而成.
比如{0011},{},{0100111}都是{0,1}^*

并且, Concatenation也是有点注意的地方的: 如果合集B是个空集, 则A◦B也会是空集, 因为无法从B中选择任何元素, 所以也组成不了任何东西

对于一个NFA, 它有五个元组:

由于NFA的节点转移时不会包含所有的字符, 所以在画表格来表示的时候, 需要在没有转移的时候写一个空集符号来表示这个字符在这个节点不会转移(或者说在这读到这个字符就会结束)

比如我们想设计一个NFA, 它只接受一个string, 它的倒数第三个字符是1:

假设: 如果有一个NFA - M认识语言A, 则存在一个DFA - M'认识A

对于1, a是对于{a}的简写, 也就是一个只包含a字符的语言.
对于◦, 这个也有简写: 可以把它省略掉, 直接写R1R2, 就表示两个语言的连接

例子:

理论: 如果一个语言是regular的, 则一定有一个正则表达式可以表达它

Lamma1:
如果存在一个正则表达式, 则我们可以把它画成一个NFA (可以表明它是regular的)

想证明这个是可以做到的: 可以把上面的Regular expression的组成的6个基础部分都化成NFA, 那么不管正则表达式有多复杂, 总有NFA可以表达出来.

6个组成部分分为两个部分:

Atomic很简单, NFA可以轻易画出来, Composite也很简单 - 可以用closure constructions来证明

Lamma2:
如果存在一个正则语言, 则一定存在一个正则表达式表达出来它.

这个证明比较复杂, 我们需要一个GNFA来证明. 这个跟NFA不同的是, 它的每条路线(状态转移方程)是可以由正则表达式来表达的.

然后, 还需要多个个Special form假设:

通过上面的三条操作, 就可以把一个GNFA来转化成一个special form的GNFA. 然后我们的目标就是把它变成一个正则表达式.

这可以用数学归纳法来归纳含有k个state的GNFA图G.
Basis: k = 2
这时候, 只有两个state, 起始点不是accept state, 然后用一个Regex (r)连接一个accept state. 答案很明显, 我们想找的正则表达式R就是状态转移方程r

Incudtion step: k > 2
我们会假设k-1个state都是可以转化成正则表达式的(数学归纳法原理), 然后需要证明有k个state也可以转换成Regex.
对于一个k state的Machine, 我们可以去掉一个非起始非结束的state, 变成一个k-1 state的 Machine. 但由于我们删掉一个点, 这个Machine就已经不等同于之前的Machine了, 所以我们需要把这个新Machine进行修改, 这样它又变成了以前的Machine, 唯一的区别就是少了一个state.
我们可以这么修复: 假设从o->p->q, 他们的转移方程分别是r1和r2, 我们删掉了p state. 我们可以直接把o state 连接q state, 然后用一个正则表达式r1r2(两个表达式连接起来)连接o和q. 这样, 就可以保证这个machine 和原来的machine认识的语言是一样的. 如果被删掉的p state还会指向自己, 则可以在r1r2表达式中间加上个r*, 表示中间夹多少个这个转移方程都没关系.
通过重复这样的操作, 我们需要把所有指向p state的state都用正则表达式连接到新的state.

Induction Conclusion: 因为Base case和 Induction Step都证明过, 所以这个假设成立

GNFA -> Regex:
上面已经证明了一个GNFA可以转化成表达式, 那么来实际操作一下:
实际操作就是一直在重复Induction Step里的东西: 一直去删除图中的某个State, 然后把删掉一个State的GNFA修改成跟原来相同的GNFA. 重复到只有start state 和Accept state.

现在, 对于一个语言A, 我们可以用NFA, DFA或者Regex来判断它到底不是regular
但我们仍然无法设计出任何机器来识别下面的语言:
这就涉及到 None Regular Language了.

这个假设说的是对于每一个regular language, 一定有一个数字p(pumping length)
如果一个字符串属于这个语言中, 并且字符串的长度≥p, 则这个字符串合约被分成三个部分xyz. 这个xyz三个部分需要满足下面三个条件
或者说不是比如一个regular 语言A={x, y, z, w}, 这四个string的长度均没超过100, 那么我们直接说p=101, 那么这个语言直接满足Pumping Lamma
从此可以看出来, 如果想要使用这个Pumping Lamma, 就需要这个语言的字符长度至少是无限的.

Proof:

使一个DFA M 认识A语言, 然后把它的state number记作p, 然后我们选择一个长度≥p的字符串. 这个长度的字符串会让某个节点一定访问两次或以上

实践:
接下来就来看怎么证明这个语言不是regular的, 通过proof by contradiction
也就是说, 我们需要证明不管哪个p, 都会找出不满足规则的某个字符串.

首先假设它是正则的, 所以会存在一个p这样, 这个字符串s一定可以被分为三个部分xyz, 由于规则规定一定要有y, 所以我们把00001111中的一段0当作y.
虽然前两个规则可以满足, 但只要我们根据规则, 来增加y的数量, 那么这个新的字符串就不会满足规则, 因为0000 0 1111就有不相等数量的0,1了. 中间隔开的0就是第二个y
这样, 不管什么p, 都满足不了上面的要求

实践2:
上面的表示有两段字符串, 字符内容怎么排列, 怎么重复都可以. 但这两段字符串需要相等
这种情况, 我们连怎么分割都不知道.

仍然是Proof By Contradiction
可能第一想到的是用上面的测试: 然而实际上是不行的, 因为如果把y当作两个0, 就可以让字符串永远是双数.

其实, 我们可以写成这样:原理跟上面差不多其实, 这个s字符串是000...01 000...01 这样, 如果我们把y看作0, 也就是第一个重复的地方, 那么如果我们把y重复, 则后半段的字符串就不会跟前面的相等.

实践3:
我们可以说这个pumping lamma是:
由于规则2, 3, y必须是一个或多个0, 但这样的话, 如果根据规则1, 把y删掉, 则这个s则不再满足有0比1多的特点了. 因为y一定含有个0, 所以(p+1)-1=p

实践4 - 用闭包性质来证明:
有相等数量的和首先, 我们可以构建出0*1*的NFA, 就是两个节点能做到的事
根据闭包性质, 两个Regular Language做操作还会得到一个Regular Language, 也就是说A=D∩0*1*会得到一个regular的语言A, 但得到的结果是
而这个A已经被证明过不是regular的

实践5:
有双数个然后, 我们可以用下面的这个方式来永远找到一个xyz来符合pumping lamma:

但需要注意的是, 虽然不满足pumping lamma的永远不是regular language, 但满足这个的, 不一定是regular language